๐Ÿ‘ฉโ€๐Ÿ’ป 14503. ๋กœ๋ด‡ ์ฒญ์†Œ๊ธฐ

@Seongukbaek Posted March 15, 2022 ยท Updated March 15, 2022 ยท 6 min read

๋ฌธ์ œ

๋กœ๋ด‡ ์ฒญ์†Œ๊ธฐ๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ฒญ์†Œํ•˜๋Š” ์˜์—ญ์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

๋กœ๋ด‡ ์ฒญ์†Œ๊ธฐ๊ฐ€ ์žˆ๋Š” ์žฅ์†Œ๋Š” Nร—M ํฌ๊ธฐ์˜ ์ง์‚ฌ๊ฐํ˜•์œผ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ์œผ๋ฉฐ, 1ร—1ํฌ๊ธฐ์˜ ์ •์‚ฌ๊ฐํ˜• ์นธ์œผ๋กœ ๋‚˜๋ˆ„์–ด์ ธ ์žˆ๋‹ค. ๊ฐ๊ฐ์˜ ์นธ์€ ๋ฒฝ ๋˜๋Š” ๋นˆ ์นธ์ด๋‹ค. ์ฒญ์†Œ๊ธฐ๋Š” ๋ฐ”๋ผ๋ณด๋Š” ๋ฐฉํ–ฅ์ด ์žˆ์œผ๋ฉฐ, ์ด ๋ฐฉํ–ฅ์€ ๋™, ์„œ, ๋‚จ, ๋ถ์ค‘ ํ•˜๋‚˜์ด๋‹ค. ์ง€๋„์˜ ๊ฐ ์นธ์€ (r, c)๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ๊ณ , r์€ ๋ถ์ชฝ์œผ๋กœ๋ถ€ํ„ฐ ๋–จ์–ด์ง„ ์นธ์˜ ๊ฐœ์ˆ˜, c๋Š” ์„œ์ชฝ์œผ๋กœ ๋ถ€ํ„ฐ ๋–จ์–ด์ง„ ์นธ์˜ ๊ฐœ์ˆ˜์ด๋‹ค.

๋กœ๋ด‡ ์ฒญ์†Œ๊ธฐ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ž‘๋™ํ•œ๋‹ค.

  1. ํ˜„์žฌ ์œ„์น˜๋ฅผ ์ฒญ์†Œํ•œ๋‹ค.
  2. ํ˜„์žฌ ์œ„์น˜์—์„œ ํ˜„์žฌ ๋ฐฉํ–ฅ์„ ๊ธฐ์ค€์œผ๋กœ ์™ผ์ชฝ ๋ฐฉํ–ฅ๋ถ€ํ„ฐ ์ฐจ๋ก€๋Œ€๋กœ ์ธ์ ‘ํ•œ ์นธ์„ ํƒ์ƒ‰ํ•œ๋‹ค. a. ์™ผ์ชฝ ๋ฐฉํ–ฅ์— ์•„์ง ์ฒญ์†Œํ•˜์ง€ ์•Š์€ ๊ณต๊ฐ„์ด ์กด์žฌํ•œ๋‹ค๋ฉด, ๊ทธ ๋ฐฉํ–ฅ์œผ๋กœ ํšŒ์ „ํ•œ ๋‹ค์Œ ํ•œ ์นธ์„ ์ „์ง„ํ•˜๊ณ  1๋ฒˆ๋ถ€ํ„ฐ ์ง„ํ–‰ํ•œ๋‹ค. b. ์™ผ์ชฝ ๋ฐฉํ–ฅ์— ์ฒญ์†Œํ•  ๊ณต๊ฐ„์ด ์—†๋‹ค๋ฉด, ๊ทธ ๋ฐฉํ–ฅ์œผ๋กœ ํšŒ์ „ํ•˜๊ณ  2๋ฒˆ์œผ๋กœ ๋Œ์•„๊ฐ„๋‹ค. c. ๋„ค ๋ฐฉํ–ฅ ๋ชจ๋‘ ์ฒญ์†Œ๊ฐ€ ์ด๋ฏธ ๋˜์–ด์žˆ๊ฑฐ๋‚˜ ๋ฒฝ์ธ ๊ฒฝ์šฐ์—๋Š”, ๋ฐ”๋ผ๋ณด๋Š” ๋ฐฉํ–ฅ์„ ์œ ์ง€ํ•œ ์ฑ„๋กœ ํ•œ ์นธ ํ›„์ง„์„ ํ•˜๊ณ  2๋ฒˆ์œผ๋กœ ๋Œ์•„๊ฐ„๋‹ค. d. ๋„ค ๋ฐฉํ–ฅ ๋ชจ๋‘ ์ฒญ์†Œ๊ฐ€ ์ด๋ฏธ ๋˜์–ด์žˆ๊ฑฐ๋‚˜ ๋ฒฝ์ด๋ฉด์„œ, ๋’ค์ชฝ ๋ฐฉํ–ฅ์ด ๋ฒฝ์ด๋ผ ํ›„์ง„๋„ ํ•  ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ์—๋Š” ์ž‘๋™์„ ๋ฉˆ์ถ˜๋‹ค.

๋กœ๋ด‡ ์ฒญ์†Œ๊ธฐ๋Š” ์ด๋ฏธ ์ฒญ์†Œ๋˜์–ด์žˆ๋Š” ์นธ์„ ๋˜ ์ฒญ์†Œํ•˜์ง€ ์•Š์œผ๋ฉฐ, ๋ฒฝ์„ ํ†ต๊ณผํ•  ์ˆ˜ ์—†๋‹ค.

์ž…, ์ถœ๋ ฅ

์ž…๋ ฅ

  • ์ฒซ์งธ ์ค„์— ์„ธ๋กœ ํฌ๊ธฐ N๊ณผ ๊ฐ€๋กœ ํฌ๊ธฐ M์ด ์ฃผ์–ด์ง„๋‹ค. (3 โ‰ค N, M โ‰ค 50)
  • ๋‘˜์งธ ์ค„์— ๋กœ๋ด‡ ์ฒญ์†Œ๊ธฐ๊ฐ€ ์žˆ๋Š” ์นธ์˜ ์ขŒํ‘œ (r, c)์™€ ๋ฐ”๋ผ๋ณด๋Š” ๋ฐฉํ–ฅ d๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. d๊ฐ€ 0์ธ ๊ฒฝ์šฐ์—๋Š” ๋ถ์ชฝ์„, 1์ธ ๊ฒฝ์šฐ์—๋Š” ๋™์ชฝ์„, 2์ธ ๊ฒฝ์šฐ์—๋Š” ๋‚จ์ชฝ์„, 3์ธ ๊ฒฝ์šฐ์—๋Š” ์„œ์ชฝ์„ ๋ฐ”๋ผ๋ณด๊ณ  ์žˆ๋Š” ๊ฒƒ์ด๋‹ค.
  • ์…‹์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— ์žฅ์†Œ์˜ ์ƒํƒœ๊ฐ€ ๋ถ์ชฝ๋ถ€ํ„ฐ ๋‚จ์ชฝ ์ˆœ์„œ๋Œ€๋กœ, ๊ฐ ์ค„์€ ์„œ์ชฝ๋ถ€ํ„ฐ ๋™์ชฝ ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. ๋นˆ ์นธ์€ 0, ๋ฒฝ์€ 1๋กœ ์ฃผ์–ด์ง„๋‹ค. ์ง€๋„์˜ ์ฒซ ํ–‰, ๋งˆ์ง€๋ง‰ ํ–‰, ์ฒซ ์—ด, ๋งˆ์ง€๋ง‰ ์—ด์— ์žˆ๋Š” ๋ชจ๋“  ์นธ์€ ๋ฒฝ์ด๋‹ค.
  • ๋กœ๋ด‡ ์ฒญ์†Œ๊ธฐ๊ฐ€ ์žˆ๋Š” ์นธ์˜ ์ƒํƒœ๋Š” ํ•ญ์ƒ ๋นˆ ์นธ์ด๋‹ค.

์ถœ๋ ฅ

  • ๋กœ๋ด‡ ์ฒญ์†Œ๊ธฐ๊ฐ€ ์ฒญ์†Œํ•˜๋Š” ์นธ์˜ ๊ฐœ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

๐Ÿ“ Logic

class Robot { int x; int y; int dir; public Robot(int x, int y, int dir) { this.x = x; this.y = y; this.dir = dir; } }
  • ๋กœ๋ด‡ ์ฒญ์†Œ๊ธฐ์˜ ์œ„์น˜๋ฅผ ์ €์žฅํ•˜๋Š” ํด๋ž˜์Šค
public int cleanRoom(int r, int c, int d) { int cleanCount = 0; queue.add(new Robot(r, c, d)); while(!queue.isEmpty()) { Robot robot = queue.poll(); if (map[robot.x][robot.y] == 0) { map[robot.x][robot.y] = 2; cleanCount++; } if (!checkWallMethod(robot)) { moveBack(robot); } } return cleanCount; }
  • ๋ฌธ์ œ์—์„œ ์ฃผ์–ด์ง„ ์ž‘๋™ ๋กœ์ง์„ ๊ตฌํ˜„ํ•œ ๋ฉ”์†Œ๋“œ
  • Queue๋ฅผ ์ด์šฉํ•œ BFS๋ฐฉ์‹์œผ๋กœ ์ฒญ์†Œํ•  ์˜์—ญ์„ ํƒ์ƒ‰ํ•œ๋‹ค.

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.io.*; import java.util.*; class Robot { int x; int y; int dir; public Robot(int x, int y, int dir) { this.x = x; this.y = y; this.dir = dir; } } class Directions { int x; int y; public Directions(int x, int y) { this.x = x; this.y = y; } } class Room { int[][] map; int N, M; Queue<Robot> queue = new LinkedList<>(); Directions[] directions = {new Directions(-1, 0), new Directions(0, 1), new Directions(1, 0), new Directions(0, -1)}; public Room (int n, int m) { N = n; M = m; map = new int[n][m]; } public int cleanRoom(int r, int c, int d) { int cleanCount = 0; queue.add(new Robot(r, c, d)); while(!queue.isEmpty()) { Robot robot = queue.poll(); if (map[robot.x][robot.y] == 0) { map[robot.x][robot.y] = 2; cleanCount++; } if (!checkWallMethod(robot)) { moveBack(robot); } } return cleanCount; } private void moveBack(Robot robot) { int backDir = turnBack(robot.dir); int backX = robot.x + directions[backDir].x; int backY = robot.y + directions[backDir].y; if (!checkBoundary(backX, backY)) { if (map[backX][backY] != 1) { queue.add(new Robot(backX, backY, robot.dir)); } } } private boolean checkWallMethod(Robot robot) { for (int i = 0; i < 4; i++) { int nextDir = turnLeft(robot.dir); int nextX = robot.x + directions[nextDir].x; int nextY = robot.y + directions[nextDir].y; robot.dir = nextDir; if (checkBoundary(nextX, nextY)) continue; if (map[nextX][nextY] == 0) { queue.add(new Robot(nextX, nextY, nextDir)); return true; } } return false; } private boolean checkBoundary(int r, int c) { return r < 0 || r >= N || c < 0 || c >= M; } private int turnLeft(int d) { return (d + 3) % 4; } private int turnBack(int d) { return (d + 2) % 4; } } public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] line = br.readLine().split(" "); int N = Integer.parseInt(line[0]); int M = Integer.parseInt(line[1]); Room room = new Room(N, M); line = br.readLine().split(" "); int r = Integer.parseInt(line[0]); int c = Integer.parseInt(line[1]); int d = Integer.parseInt(line[2]); for (int i = 0; i < N; i++) room.map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); System.out.println(room.cleanRoom(r, c, d)); br.close(); } }

โœ๏ธ Review

  • ์‹œ๋ฎฌ๋ ˆ์ด์…˜ ๋ฌธ์ œ๋Š” ์ฃผ์–ด์ง„ ์กฐ๊ฑด์— ๋”ฐ๋ผ ๋กœ์ง์„ ๊ตฌํ˜„ํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ์ดํ•ดํ•ด, ๋กœ๋ด‡์ฒญ์†Œ๊ธฐ์˜ ์ž‘๋™์›๋ฆฌ๋งˆ๋‹ค์˜ ๋ฉ”์†Œ๋“œ๋ฅผ ๊ตฌํ˜„ํ•˜๋ ค ํ–ˆ๋‹ค.
  • ์ตœ๋Œ€ํ•œ ๊ฐ์ฒด ์ง€ํ–ฅ์ ์œผ๋กœ ๋“ค์—ฌ์“ฐ๊ธฐ ํšŸ์ˆ˜๋„ ๊ณ ๋ คํ•˜๋ฉด์„œ ๋ฉ”์†Œ๋“œ ์ถ”์ถœ์„ ์ˆ˜ํ–‰ํ–ˆ๋‹ค.

๐Ÿ“• ์ถœ์ฒ˜

Baekjoon : https://www.acmicpc.net/problem/14503

@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€